# -*- coding: utf-8 -*-

# # 基础面额1, 5, 11的货币，求能凑出w的最少纸币的数目
# # eg:
# # 15 = 5 + 5 + 5

# import sys

# # 只给出最小的组合的数目
# class Solution(object):
#     def minCount(self, target):
#         minTaget = [0] * (target + 1)
#         minTaget[1] = 1
#         for x in xrange(1, target + 1):
#             cost = sys.maxsize
#             if x - 1 >= 0:
#                 cost = min(cost, minTaget[x - 1] + 1)
#             if x - 5 >= 0:
#                 cost = min(cost, minTaget[x - 5] + 1)
#             if x - 11 >= 0:
#                 cost = min(cost, minTaget[x - 11] + 1)
#             minTaget[x] = cost
#         return minTaget[target]

# # 给出组合的解法
# class Solution(object):
#     def minCount(self, target):
#         minTaget = {}
#         minTaget[0] = {"cost" : 0, "group" : []}
#         for x in xrange(1, target + 1):
#             cost_1 = ((minTaget[x - 1]["cost"] + 1) if (x - 1 >= 0) else sys.maxsize)
#             cost_5 = ((minTaget[x - 5]["cost"] + 1) if (x - 5 >= 0) else sys.maxsize)
#             cost_11 = ((minTaget[x - 11]["cost"] + 1) if (x - 11 >= 0) else sys.maxsize)
#             cost_min = min(cost_1, cost_5, cost_11)
#             group = []
#             if cost_min == cost_1:
#                 group = minTaget[x - 1]["group"] + [1]
#             elif cost_min == cost_5:
#                 group = minTaget[x - 5]["group"] + [5]
#             elif cost_min == cost_11:
#                 group = minTaget[x - 11]["group"] + [11]
#             minTaget[x] = {"cost" : cost_min, "group" : group}
#         return minTaget[target]["cost"], minTaget[target]["group"]
# t = Solution();
# print t.minCount(28);


# 求最短路径，求从S到T的最短路径
#
#                   ---(30)---"C"---|---(20)----
#                   |               |          |
#                   |               |          |
#                   |               |          |
#     ---(10)---"A"-|               |          |
#     |             |              (5)        "T"
#     |             |               |          |
#     |             |               |          |
# "S"-|             ---(10)----     |          |
#     |                       |     |          |
#     |                       |----"D"----------
#     |                       |
#     ---(20)---"B"----(20)----

class Solution(object):
    def minPath(self):
